package com.benben.springSecurity.weiwei;

public class InsertValInLinke {
    class Node {
        public int val;
        public Node next;
        public Node(){}
        public Node (int _val){
            val = _val;
        }
        public Node(int _val,Node _next){
            val = _val;
            next = _next;
        }
    }
    //1,头结点如果是空的，构造单节点循环链表返回
    //2，寻找符合升序条件的结点，在过程中记录最大值
    //3，没有满足升序的结点，将insertVal插入到最大值节点后面
    public Node insert(Node head,int insertVal){
        Node ins = new Node();
        ins.val = insertVal;
        if(null == head){
            ins.next = ins;
            return ins;
        }
        Node max = head;
        Node temp = head;
        while(temp.next != head){
            Node next = temp.next;
            if(temp.val<=insertVal && insertVal<=next.val){
                temp.next = ins;
                ins.next = next;
                return head;
            }
            temp = next;
            if(temp.val >= max.val){
                max = temp;
            }
        }
        if(temp.val<=insertVal && insertVal<=temp.next.val){
            Node next = temp.next;
            temp.next = ins;
            ins.next = next;
            return head;
        }
        Node next = max.next;
        max.next = ins;
        ins.next = next;
        return head;

    }

}
